#include "Algorithm.h"

/**
 * the constructor of GoBangAlgorithm, doing nothing
 */
GoBangAlgorithm::GoBangAlgorithm() {
}

/**
 * a private function to reverse the string in function SubStringMix and GoBangScanner
 * @param str a string
 * @return the string which reversed from the string str
 */
string GoBangAlgorithm::StringReverse(string str) {
    string tmp = "";
    for (int i = str.length()-1; i >= 0; i--) {
        tmp += str.at(i);
    }
    return tmp;
}

/**
 * a private function to remix the two substring in function GoBangScanner
 * @param left left substring in function GoBangScanner
 * @param right right substring in function GoBangScanner
 * @return the hole string
 */
string GoBangAlgorithm::SubStringMix(string left, string right) {
    return StringReverse(left) + right;
}

/**
 * a private function to convert string to char array
 * @param str a string
 * @return the char array translated from str
 */
char * GoBangAlgorithm::StringToCharArr(string str) {
    char *arr = new char[str.length()];
    for (int i = 0; i < str.length(); i++) {
        arr[i] = str.at(i);
    }
    return arr;
}

/**
 * a private function to translate ChessNode to string in function GoBangScanner
 * @param a ChessNode which need to translate
 * @param r ChessRoute which include the Node a
 * @return a string translated from Node a
 */
string GoBangAlgorithm::ChessNodeTranslate(ChessNode a, ChessRoute r) {
    if (a.PLAYERID() == r.showFirstPlayerID()) {
        return "f";
    }
    else if (a.PLAYERID() == r.showNextPlayerID()) {
        return "n";
    }
    else {
        return "?";
    }
}

/**
 * DFS Searcher which can judge if any player has won. TIPS: don't use it!
 * @param Board ChessBoard
 * @param ScanNode the Node to search begin
 * @param Location_X the ScanNode's origin location x
 * @param Location_Y the ScanNode's origin location y
 * @param Count the count of the same Node, if Count up to five, return the playerid
 * @param Size the Size of the Board
 * @param Mode the direction of the search move
 * @param Step the step which the function has searched, if Step up to five, return zero
 * @return return winner's playerid if search succeed, or return zero
 */
int GoBangAlgorithm::GoBangWinnerScanner(ChessNode **Board, ChessNode ScanNode, int Location_X, int Location_Y, int Count, int Size, int Mode, int Step) {
    int MoveVector[8][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};
    if (Count == 5) {
        return ScanNode.PLAYERID();
    }
    if (Step >= 5) {
        return 0;
    }
    if (Board[Location_X][Location_Y].PLAYERID() == ScanNode.PLAYERID()) {
        return GoBangWinnerScaner(Board,ScanNode,Location_X+MoveVector[Mode][0],Location_Y+MoveVector[Mode][1],Count+1,Size,Mode,Step+1);
    }
    else {
        return 0;
    }
}

/**
 * a function to scan the latest step's nearby lines, translate them to string
 * @param ScanNode a ChessNode need to be scant
 * @param Board a ChessBoard
 * @param r a ChessRoute which include ScanNode
 * @param Size the Size of the Board
 * @return string array which translated from the ChessBoard
 */
string * GoBangAlgorithm::GoBangScanner(ChessNode ScanNode, ChessNode **Board, ChessRoute r, int Size) {
    string *arr = new string[8];
    for (int i = 0; i < 4; i++) {
        arr[i] = "";
    }
    // arr[0]: -
    for (int i = 1; i <= Size; i++) {
        arr[0] += ChessNodeTranslate(Board[ScanNode.LOCATION()[0]][i],r);
    }

    // arr[1]: |
    for (int i = 1; i <= Size; i++) {
        arr[1] += ChessNodeTranslate(Board[i][ScanNode.LOCATION()[1]],r);
    }

    // arr[2]: /
    for (int i = ScanNode.LOCATION()[0], j = ScanNode.LOCATION()[1]; i <= Size && j >= 1; i++, j--) {
        arr[2] += ChessNodeTranslate(Board[i][j],r);
    }
    string tmp2 = arr[2]; arr[2] = "";
    for (int i = ScanNode.LOCATION()[0]-1, j = ScanNode.LOCATION()[1]+1; i >= 1 && j <= Size; i--, j++) {
        arr[2] += ChessNodeTranslate(Board[i][j],r);
    }
    arr[2] = SubStringMix(tmp2, arr[2]);

    // arr[3]: "\"
    for (int i = ScanNode.LOCATION()[0], j = ScanNode.LOCATION()[1]; i >= 1 && j >= 1; i--, j--) {
        arr[3] += ChessNodeTranslate(Board[i][j],r);
    }
    string tmp3 = arr[3]; arr[3] = "";
    for (int i = ScanNode.LOCATION()[0]+1, j = ScanNode.LOCATION()[1]+1; i <= Size && j <= Size; i++, j++) {
        arr[3] += ChessNodeTranslate(Board[i][j],r);
    }
    arr[3] = SubStringMix(tmp3,arr[3]);

    for (int i = 4; i < 8; i++) {
        arr[i] = StringReverse(arr[i-4]);
    }

    return arr;
}

/**
 * the KMP algorithm to compare the StrLong and StrShrot, if StrLong's substring equals to StrShort, return true
 * @param StrLong the long string
 * @param StrShort the short string
 * @return if StrLong's substring equals to StrShort, return true, or return false
 */
bool GoBangAlgorithm::bKMP(string StrLong, string StrShort) {
    char* StrLongArr = StringToCharArr(StrLong);
    char* StrShortArr = StringToCharArr(StrShort);
    for (int i = 0; i < StrLong.length();) {
        int tmp = i;
        for (int j = 0; j < StrShort.length();) {
            if (StrLongArr[i] == StrShortArr[j]) {
                i++; j++;
                if (j == StrShort.length()) {
                    return true;
                }
            }
            else {
                i = tmp+1; j = 0;
                break;
            }
        }
    }
    return false;
}

/**
 * the KMP algorithm to compare the StrLong and StrShrot, if StrLong's substring equals to StrShort, return its count
 * @param StrLong the long string
 * @param StrShort the short string
 * @return the count of the substring matched StrShort
 */
int GoBangAlgorithm::iKMP(string StrLong, string StrShort) {
    int count = 0;
    char* StrLongArr = StringToCharArr(StrLong);
    char* StrShortArr = StringToCharArr(StrShort);
    for (int i = 0; i < StrLong.length();) {
        int tmp = i;
        for (int j = 0; j < StrShort.length();) {
            if (StrLongArr[i] == StrShortArr[j]) {
                i++; j++;
                if (j == StrShort.length()) {
                    count += 1;
                    i = tmp+1; j = 0;
                    break;
                }
            }
            else {
                i = tmp+1; j = 0;
                break;
            }
        }
    }
    return count;
}

int GoBangAlgorithm::GoBangJudger(ChessRoute r, ChessNode **Board, int Size) {
    bool isFirstPlayer = (r.RecentStep().PLAYERID() == r.showFirstPlayerID());
    string* ScanRoute = GoBangScanner(r.RecentStep(),Board,r,Size);
    if (isFirstPlayer) {
        // 判断长连禁手
        bool tmpc[4] = {false}; bool tag = false;
        for (int i = 0; i < 4; i++) {
            if (bKMP(ScanRoute[i],"ffffff")) {
                tmpc[i] = true;
                tag = true;
            }
        }
        for (int i = 0; i < 4; i++) {
            if (tmpc[i] == false) {
                if (bKMP(ScanRoute[i],"fffff")) {
                    return r.showFirstPlayerID();
                }
            }
        }
        if (tag) {
            return r.showNextPlayerID();
        }

        // 判断胜负
        for (int i = 0; i < 4; i++) {
            if (bKMP(ScanRoute[i],"fffff")) {
                return r.showFirstPlayerID();
            }
        }

        string BannedRoute3[] = {"?fff?","?ff?f?"};
        double BannedRouteWeight3[] = {0.5,1};
        string BannedRoute4[] = {"fff?f","nffff?","ffff?n","?ffff?"};
        double BannedRouteWeight4[] = {1,1,1,0.5};

        // 判断三三禁手
        double Weight3 = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 2; j++) {
                Weight3 += BannedRouteWeight3[j]*iKMP(ScanRoute[i],BannedRoute3[j]);
            }
        }
        if (Weight3 > 1.1) {
            return r.showNextPlayerID();
        }

        // 判断四四禁手
        double Weight4 = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 4; j++) {
                Weight4 += BannedRouteWeight4[j]*iKMP(ScanRoute[i],BannedRoute4[j]);
            }
        }
        if (Weight4 > 1.1) {
            return r.showNextPlayerID();
        }
    }
    else {
        for (int i = 0; i < 8; i++) {
            if (bKMP(ScanRoute[i],"nnnnn")) {
                return r.showNextPlayerID();
            }
        }
    }
    return -1;
}